package pers.qianyu.month_202101.date_20210111;

/**
 * 200. 岛屿数量
 * https://leetcode-cn.com/problems/number-of-islands/
 *
 * @author mizzle rain
 * @date 2021-01-11 15:10
 */
public class NumIslands {
    int[][] dxy = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public int numIslands(char[][] grid) {
        int h = grid.length;
        if (h == 0) return 0;
        int w = grid[0].length;
        if (w == 0) return 0;
        int count = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                char ch = grid[i][j];
                if (ch == '1') {
                    count++;
                    paint(grid, i, j);
                }
            }
        }
        return count;
    }

    private void paint(char[][] grid, int i, int j) {
        int h = grid.length;
        int w = grid[0].length;
        grid[i][j] = '0';
        for (int[] d : dxy) {
            int x = d[0] + i, y = d[1] + j;
            if (x >= 0 && y >= 0 && x < h && y < w && grid[x][y] == '1') {
                paint(grid, x, y);
            }
        }
    }
}
